

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

#include "common/utils.hpp"

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int x) : val(x), left(nullptr), right(nullptr), next(nullptr) {}
    Node(int x, Node* l, Node* r, Node* n)
        : val(x), left(l), right(r), next(n) {}
};

// 填充每个节点的下一个右侧节点指针（和116的区别：没有限制要是满二叉树但是代码其实和116一模一样）
// 双指针
Node* connect(Node* root) {
    std::queue<Node*> queue;

    if (root != nullptr) queue.push(root);

    while (!queue.empty()) {
        int size = queue.size();
        Node* preNode;
        Node* currNode;
        for (int i = 0; i < size; i++) {
            currNode = queue.front();
            queue.pop();

            if (i > 0) {
                preNode->next = currNode;
            }
            preNode = currNode;

            if (currNode->left) queue.push(currNode->left);
            if (currNode->right) queue.push(currNode->right);
        }
    }

    return root;
}

std::vector<std::string> traverseNode(Node* root) {
    std::vector<std::string> result;
    std::queue<Node*> queue;

    if (root != nullptr) queue.push(root);

    while (!queue.empty()) {
        Node* node = queue.front();
        queue.pop();
        std::string str = std::to_string(node->val);
        if (node->next == nullptr) {
            str += ("->#");
        } else {
            str += ("->" + std::to_string(node->next->val));
        }
        result.push_back(str);

        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
    }

    return result;
}

/*
              10
        6          16
      3   NULL  14    19  
*/
Node* node =
    new Node(10, new Node(6, new Node(3), nullptr, nullptr),
             new Node(16, new Node(14), new Node(19), nullptr), nullptr);

int main() {
    Node* root = connect(node);
    std::vector<std::string> res = traverseNode(root);
    for (int i = 0, size = res.size(); i < size; i++) {
        std::cout << res[i] << " ";
    }
    std::cout << "\n";
}